package Utils;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Random;

public class Utils {
    /**
     * 基本快速排序
     *
     * @param start 此次调用需要处理的范围的左边界（包含）
     * @param end   此次调用需要处理的范围的左边界（不包含）
     */
    public static void quickSort(int[] nums, int start, int end) {
        if (end <= start) return;

        int pivot = nums[start];
        int left = start, right = end - 1;
        int pivotIdx = start;
        while (left < right) {
            while (left < right && nums[right] >= pivot) right--;
            if (left < right) {
                nums[left++] = nums[right];
                pivotIdx = right;
            }
            else break; // 指针重合
            while (left < right && nums[left] <= pivot) left++;
            if (left < right) {
                nums[right--] = nums[left];
                pivotIdx = left;
            }
            else break;
        }

        nums[pivotIdx] = pivot;
        quickSort(nums, start, pivotIdx);
        quickSort(nums, pivotIdx + 1, end);
    }

    public static void quickSort(int[] nums) {
        quickSort(nums, 0, nums.length);
    }

    /**
     * 获取一个带有小写元音字母的集合
     */
    public static HashSet<Character> getVowelSet() {
        HashSet<Character> vowels = new HashSet<>();
        vowels.add('a');
        vowels.add('e');
        vowels.add('i');
        vowels.add('o');
        vowels.add('u');
        return vowels;
    }

    /**
     * 快速选择第k大的元素（k从1开始）。期望时间复杂度：O(N)。
     */
    public static int quickSelect(int[] nums, int k, int start, int end) {
        int n = nums.length;
        if (k > n) throw new IllegalArgumentException("k larger than nums.length");

        Random r = new Random();
        int randomIdx = r.nextInt(end - start);
        swap(nums, start, randomIdx + start); // 应对退化情形
        int pivot = nums[start];
        int i = start, j = end - 1;
        while (i < j) {
            while (i < j && nums[j] >= pivot) j--;
            if (i < j) nums[i] = nums[j];
            while (i < j && nums[i] <= pivot) i++;
            if (i < j) nums[j] = nums[i];
        }
        if (i == n - k) return pivot;
        nums[i] = pivot;
        if (i < n - k) return quickSelect(nums, k, i + 1, end);
        else return quickSelect(nums, k, start, i);
    }

    public static int quickSelect(int[] nums, int k) {
        return quickSelect(nums, k, 0, nums.length);
    }

    public static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    /**
     * 将十进制非负整数转为二进制位的队列。队列中的元素只为0或1。将队列中的元素依次出队，先出队的元素位于低位，可以得到该十进制数的二进制表示。
     */
    private static LinkedList<Integer> decimal2BinaryQueueNonNegative(int decimal, int minNumDigits) {
        int remainder = decimal;
        LinkedList<Integer> queue = new LinkedList<>();
        while (remainder > 0) {
            queue.offer(remainder % 2);
            remainder /= 2;
        }
        int repeat = minNumDigits - queue.size();
        // 前端补0
        for (int i = 1; i <= repeat; i++) {
            queue.addLast(0);
        }

        return queue;
    }
}
